<?php
/**
 * User: LRZ
 * Date: 2020/1/13
 * Time: 17:19
 */

/**
 *  268. 缺失数字
 *
 *  标签：位运算、数组、数学
 *
 *  给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 *
 *  示例 1:
 *  输入: [3,0,1]
 *  输出: 2
 *
 *  示例 2:
 *  输入: [9,6,4,2,3,5,7,0,1]
 *  输出: 8
 *
 *  说明:
 *  你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/missing-number
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$nums = [0, 1];
$res  = missingNumber($nums);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function missingNumber($nums)
{
    $missing = count($nums);
    sort($nums);
    foreach ($nums as $i => $iValue) {
        $missing ^= $i ^ $iValue;
    }
    return $missing;
}